package com.algrithom.unionfind;

/**
 * 684——冗余连接 200 737 1102 1135 261 1061 323 924
 *
 * @author think
 * @version 1.0.0
 * @since 2020/5/7
 */
public class Solution2 {
    
    public static void main(String[] args){
        
    }
    
    private static int find(int[] parent,int x){
        int node = x;
        while (parent[node] != node) {
            node = parent[node];
        }
        return node;
    }
    
    private static void union(int[] parent,int x,int y){
        int parentX = find(parent,x);
        int parentY = find(parent,y);
        if (parentX != parentY) {
            parent[parentY] = parentX;
        }
    }
    
    public static int[] findRedundantConnection(int[][] edges){
        int len = edges.length;
        int[] parent = new int[len + 1];
        for (int i = 1; i < len + 1; i++) {
            parent[i] = i;
        }
        
        for (int[] edge : edges) {
            if (find(parent,edge[0]) == find(parent,edge[1])) {
                return edge;
            } else {
                union(parent,edge[0],edge[1]);
            }
        }
        
        return new int[0];
    }
}
